package _18_剑指OfferII;

import java.util.*;

public class _075_剑指OfferII数组相对排序 {

    public static void main(String[] args) {

        _075_剑指OfferII数组相对排序 v = new _075_剑指OfferII数组相对排序();

        int[] arr1 = {2,3,1,3,2,4,6,7,9,2,19};
        int[] arr2 = {2,1,4,3,9,6};
        System.out.println(Arrays.toString(v.relativeSortArray(arr1, arr2)));
    }

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        SortedMap<Integer, Integer> map = new TreeMap<>();
        for (int i : arr1) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        int[] results = new int[arr1.length];
        int index = 0;
        for (int i : arr2) {
            int count = map.remove(i);
            while (count-- > 0) {
                results[index++] = i;
            }
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int count = entry.getValue();
            int key = entry.getKey();
            while (count-- > 0) {
                results[index++] = key;
            }
        }
        return results;
    }

}
